1. Field of the Invention
This invention relates to variable length coding and circuits for coding and decoding of information using variable length codes.
2. Description of Related Art
Information can be transmitted or stored digitally as a series of bits. Often, the series of bits represents a string of symbols which is created and interpreted according to a predefined syntax for the information. According to the syntax, each symbol in the string has a fixed number of possible values or meanings. Fixed length coding represents the value of a symbol using a number of bits that is fixed for the symbol and independent of the symbol's value. For example, symbols having 256 possible values are typically represented by eight bits 00h to FFh. More or fewer bits may be used for symbols having more or fewer possible values.
Typically, the choice of syntax and the nature of the information represented cause some symbol values to occur more frequently than other symbol values. Variable length coding codes different values of a symbol using different numbers of bits. One well known variable length coding technique, commonly referred to as Huffman coding, matches each symbol value to a Huffman code in a table for the symbol. The most common symbol values have the Huffman codes with the fewest bits, and rarer symbol values have Huffman codes containing more bits. Replacing fixed length codes with Huffman codes reduces the average number of bits required to express strings of symbols.
Arithmetic coding is a variable length coding technique that uses an arithmetic coding model to encode a string of symbols. FIG. 1 illustrates an example of arithmetic coding. In the example, each symbol has six possible values {a, e, i, o, u, !}, and the string encoded is "eaii!". An arithmetic coding model divides an interval into segments which have lengths proportional to the probability of a symbol value occurring in a string. In FIG. 2, the probabilities for symbol values a, e, i, o, u, and ! are 20%, 30%, 10%, 20%, 10%, and 10%; and the model divides the interval [0,1) into segments [0,0.2), [0.2,0.5), [0.5,0.6), [0.6,0.8), [0.8,0.9), and [0.9,1.0) which correspond to symbol values a, e, i, o, u, and ! respectively.
To determine an arithmetic code for string "eaii" interval [0,1) is divided according to the model, and a segment [0.2,0.5) corresponding to symbol value e, the first symbol value in string eaii!, is selected. The selected segment is also an interval which contains the arithmetic code and is divided according to the model into segments [0.2,0.26), [0.26,0.35), [0.35,0.38), [0.38,0.44), [0.44,0.47), and [0.47,0.5) corresponding to symbol values a, e, i, o, u, ! respectively. The segment [0.2,0.26) corresponding to symbol value a, the second symbol value in string "eaii", is selected. Partitioning and selecting segments is repeated for symbol values i, i, and ! and results in selection of interval [0.23354,0.2336). Any value in interval [0.23354,0.2336) can be used as an arithmetic code which identifies string "eaii!". A preferred code requires the minimum number of bits to express. For the example, a code value 0.233581542 in interval [0.23354,0.2336) is 0.0011101111011 binary.
Prior art arithmetic codes describe strings containing a single symbol type. When the syntax calls for a change of symbol type, coding is interrupted. Many syntaxes define many types of symbols, and each type of symbol has different statistics from the other types of symbols. The prior art has not provided a way to employ continuous arithmetic coding in applications such as moving image encoding where strings contain varied types of symbols having different ranges of possible values and different statistics.